Computer networks rely on infrastructure components that establish data communication links with other devices. Many computer networks include a firewall configured to monitor and control the flow of data within the network. Often, the firewall is implemented by an infrastructure component, such as a router or switch. The firewall inspects network traffic passing through the infrastructure component, and controls the flow of traffic based on a set of rules, also known as an access control list (ACL). The rules specify how a packet should be handled based on the value(s) of one or more fields or attributes associated with the packet, such as, for example, the source IP address, source port, destination IP address, destination port, and the like. A network administrator may configure the firewall by defining the rules and the infrastructure component then handles packets by comparing the fields or attributes of the packet to the set of rules. For example, a router or switch may receive a packet, and permit or deny further transmission of the packet by comparing the source IP address associated with the packet to one or more rules.
Generally, the process of looking up and applying rules is one of the most frequently performed operations in a firewall. As a result, the overall performance of the firewall, and thus the performance of the underlying infrastructure component (e.g., a router or switch) implementing the firewall, depends on the speed and efficiency of the rule lookup. There may be as many as a few hundred or more different rules defined in the set of rules (or ACL). As a result, it is impractical or inefficient to implement the set of rules using a linear list, for example, because of the amount of time that may be required to traverse and compare each rule to a received packet (e.g., worst case time of O(n)). Additionally, because the rules of the set of rules may span various combinations and/or ranges of multiple fields of the packet (e.g., source IP address, destination IP address, source port, destination port), other conventional data structures such as binary trees are also inadequate.
In order to improve the rule lookup process, some current systems implement the set of rules using a tree data structure. However, because of the number of fields and the range of values that the rules span, along with the number of rules in the set of rules, it is difficult to arrive at an optimal tree without iteratively constructing a number of different trees and analyzing the performance of each one. Thus, prior art systems use one or more heuristics to create a tree by dividing or splitting the set of rules among one or more fields and assigning subsets of the set of rules to child nodes. However, prior art methods are inefficient and result in search trees with increased memory or storage requirements.